A computer network typically comprises a plurality of interconnected devices. These devices may include any network device, such as a server or end station, that transmits or receives data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs may employ a data communication protocol, such as Ethernet or token ring, that defines the functions performed by the data link and physical layers of a communications architecture in the LAN. In many instances, several LANs are interconnected by point-to-point links, microwave transceivers, satellite hookups, etc. to form a wide area network (“WAN”) that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a bridging function between two or more LANs. Alternatively, a switch may be utilized to provide a switching function for transferring information among a plurality of LANs or end stations. In effect, a switch is a bridge among more than two networks or entities. The terms “bridge” and “switch” will be used interchangeably throughout this description. Bridges and switches are typically devices that operate at the Data Link layer (“layer 2”) of the Open Systems Interconnection (“OSI”) model. Their operation is defined in the American National Standards Institute (“ANSI”) Institute of Electrical and Electronics Engineers (“IEEE”) 802.1D standard. A copy of the ANSI/IEEE Standard 802.1D, 1998 Edition, is incorporated by reference herein in its entirety.
Telecommunication traffic among network devices is divided into seven layers under the OSI model and the layers themselves split into two groups. The upper four layers are used whenever a message passes to or from a user. The lower three layers are used when any message passes through the host computer, whereas messages intended for the receiving computer pass to the upper four layers. “Layer 2” refers to the data-link layer, which provides synchronization for the physical level and furnishes transmission protocol knowledge and management.
Networks may be designed using a plurality of distinct topologies—that is, the entities in the network may be coupled together in many different ways. Referring to FIGS. 1-3, there are shown different examples of “ring” topologies. A ring topology is a network configuration formed when “Layer 2” bridges are placed in a circular fashion, with each bridge having two and only two ports belonging to a specific ring. FIG. 1 shows a single ring 150 having bridges 152 connected by paths 154. Each bridge 152 in ring 150 in FIG. 1 has two ports 152a and 152b belonging to the ring. FIG. 2 shows two adjacent rings, 150a and 150b, with a single bridge 156 having two ports 156a, 156b belonging to each ring.
In FIGS. 1 and 2, no paths or bridges are shared among rings. In FIG. 3 two rings 150c and 150d are connected and share two bridges 158, 160. Bridge 158 has two ports 158a and 158b which each uniquely belong to only one ring, rings 150c and 150d respectively. Bridge 158 also has one port 158c connected to a path which is shared by both rings 150c and 150d. If rings are assigned different priority levels, a port such as 158c connected to the shared link assumes the priority value of the higher priority ring, and ports 158a and 158b in shared bridge 158 and port 160a in bridge 160 connected to the lower priority ring are deemed to be customer (or lower priority) ports. The use of a shared link between shared bridges 158, 160 allows for the connection of rings and the growth of a larger network from smaller ring components; however, the shared link also presents difficulties since its failure affects both rings 150c and 150d. 
Ring topologies shown in FIGS. 1-3 present Layer 2 traffic looping problems. As illustrated in FIG. 4, in a single ring topology, data traffic can circulate around in either direction past their origination and thus create repetition of messages. For example, data traffic may originate in bridge 151, travel counter-clockwise in the ring, pass bridge 157 and return to bridge 151. This is called a loop. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, because switches and bridges replicate, e.g. flood, frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.
To prevent looping, one of the paths in the ring is blocked, as shown in FIG. 4, by blocking data traffic in one of the ring ports—in this case, either port 151a or 157a. The port is deemed to be in a “blocking” state, in which it does not learn or forward incoming or outgoing traffic.
A network may be segregated into a series of logical network segments. For example, any number of physical ports of a particular switch may be associated with any number of other ports by using a virtual local area network (“VLAN”) arrangement that virtually associates the ports with a particular VLAN designation. Multiple ports may thus form a VLAN even though other ports may be physically disposed between these ports.
The VLAN designation for each local port is stored in a memory portion of the switch such that every time a message is received by the switch on a local port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the local port where the message originated.
Most networks include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. For example, in the ring networks shown in FIGS. 1-4, if communication is blocked preventing data from flowing counterclockwise, the data may still reach its destination by moving counter-clockwise. The existence of redundant links, however, may also cause the formation of loops within the network.
To avoid the formation of loops, many network devices execute a “spanning tree algorithm” that allows the network devices to calculate an active network topology which is loop-free (e.g. has a needed number of ports blocked) and yet connects every element in every VLAN within the network. The IEEE 802.1D standard defines a spanning tree protocol (“STP”) to be executed by 802.1D compatible devices (e.g., bridges, switches, and so forth). In the STP, Bridge Protocol Data Units (“BPDUs”) are sent around the network and are used to calculate the loop free network technology.
The spanning tree protocol, defined in IEEE 802.1, is used by bridges in a network to dynamically discover a subset of the network topology that provides path redundancy while preventing loops. Spanning tree protocol provides redundancy by defining a single tree that spans the bridges and maintains all other paths and connections in a standby or blocked state. The protocol allows bridges to transmit messages to one another to thereby allow each bridge to select its place in the tree and which states should be applied to each of its ports to maintain that place. For example, a port in a given bridge that is connected to an active path at a given time is kept in a forwarding state in which all data traffic is received and transmitted to the next portion of the network; ports in the bridge that are connected to inactive paths are kept in a non-forwarding state, such as a blocking state, in which traffic is blocked through that port.
Bridges in a spanning tree network pass bridge protocol data units, or “BPDU”s, amongst themselves. Each BDPU comprises information including root, bridge and port identifiers, and path cost data (all discussed below). This information is used by the bridges, to “elect” one of the bridges in the spanning tree network to be a unique “root bridge” for the network, calculate the shortest least cost path, e.g. distance, from each bridge to the root bridge, select which ports will be blocking, and for each LAN, elect one of the bridges residing in the LAN to be a “designated bridge”.
In brief, the election of a root bridge is performed by each bridge initially assuming itself to be the root bridge. Each bridge transmits “root” BPDUs and compares its BDPU information with that received from other bridges. A particular bridge then decides whether to stop serving as a root and stop transmitting BPDUs when the configuration of another bridge is more advantageous to serve as the root than the particular bridge. Ports are converted from blocking to forwarding states and back again and undergo several possible transition states depending upon the BPDUs received. Once the bridges have all reached their decisions, the network stabilizes or converges, thereby becoming loop-free. A similar process is followed after a link failure occurs in the network. In that case, a new root and/or new active paths must be identified. An overview of the spanning tree protocol, which is well known to those of skill in the art, can be found at http://standardsieee.org/getieee802/download/802.1D-1998.pdf, pages 58-109 and is herein incorporated by reference in its entirety.
Other available loop avoidance protocols include that shown and described in now pending NETWORK CONFIGURATION PROTOCOL AND METHOD FOR RAPID TRAFFIC RECOVERY AND LOOP AVOIDANCE IN RING TOPOLOGIES, filed Mar. 4, 2002, Ser. No. 10/090,669, now U.S. Pat. No. 6,717,922, issued Apr. 6, 2004, and now pending SYSTEM AND METHOD FOR PROVIDING NETWORK ROUTE REDUNDANCY ACROSS LAYER 2 DEVICES, filed Apr. 16, 2002, Ser. No. 10/124,449. The entirety of these applications is hereby incorporated by reference.
All of the current protocols require devices in a network to be protocol-aware. That is, each device must be able to run and understand the protocol that is globally running in the network. A misconfigured protocol or malfunctioning device could potentially cause a loop that would impact the whole network.
To illustrate this problem, referring to FIG. 5, there is shown a network 180 comprising a core or higher priority network such as a provider 170 coupled to a customer or lower priority network 172 with a lower priority through a switch 174. Core network 170 runs a conventional spanning tree protocol to avoid loops and has defined a blocked path 176. This means that either port 178 or port 180 is blocked. Many different causes may result in involuntary loops which may collapse the entire network 180 including: STP corrupted BPDUs, unidirectional optical fibers which result, for example, when paths which typically comprise two optical fibers have one optical fiber shut down, and non-configured protocols in loop topologies. In the example in FIG. 5, someone in customer network 172 has improperly disabled the STP running in network 172 or, the STP has become disabled due to problems just mentioned. As a consequence, even though core network 170 is properly running the STP to avoid loops, since the customer in network 172 is not running the STP, a loop is created in customer network 172 and packets from customer network 172 flood core network 170. As core network 170 and customer network 172 share the same data domain, core network 170 will be flooded with customer packets and will be affected adversely by the customer's action. Yet, it is not possible to ensure that all network administrators or devices are properly doing their respective jobs and running respective STPs. Provider networks may form the core network for entire countries or even continents. These provider networks should not be affected by fluctuations in customer networks.
In the application NETWORK CONFIGURATION PROTOCOL AND METHOD FOR RAPID TRAFFIC RECOVERY AND LOOP AVOIDANCE IN RING TOPOLOGIES, (referenced above) a network configuration protocol allows for de-coupling of customer networks and provider networks running distinct instances of a STP. In brief, in a large ring network comprising first and second rings connected through the shared use of a bridge, the first and second rings are assigned a lower relative priority, e.g. a customer, and a higher relative priority, e.g. a provider. Control packets for the lower priority ring are sent through the entire large ring. Control packets for the higher priority ring are sent only through the higher priority ring. In the event that the shared bridge fails, the lower priority ring maintains its status as its control packets continue to circulate the large ring. The higher priority ring detects the failure and adjusts ports accordingly.
However, if the lower priority network does not run some form of loop prevention/avoidance protocol to detect loops, loops will occur and will affect the provider network.
A method for resolving this issue is shown in U.S. patent application Ser. No. 10/456,756, entitled “System and Method for Multiple Spanning Tree Protocol Domains in a Virtual Local Area Network” by Rajiv Ramanathan and Jordi Moncada-Elias filed Jun. 9, 2003, the entirety of which is hereby incorporated by reference. In that application, multiple loop detection protocols are provided for each VLAN. This prevents “layer 2” loops by running a customer side spanning tree protocol from a provider network.
However, there is a need in the art for a system and method to protect a provider network when a customer network attached to it does not run a loop avoidance protocol even when the customer network is connected across multiple domains.